1. Field of the Invention
The present invention relates to a system and method for signal demodulation, particularly to a system and method for reducing the computational complexity of demodulating a signal.
2. Background and Objects of the Present Invention
Digital wireless communication systems are used to convey a variety of information between remotely located users. With digital communications, such information is translated into a digital or binary form, commonly referred to as bits, for communications purposes. A transmitter maps this bit stream into a modulated symbol stream, which is detected at a digital receiver and mapped back into bits whereby information content is conveyed.
In digital wireless communications, however, the radio environment presents many difficulties that impede successful communications. One difficulty is that the signal level can fade as a result of the signal traveling multiple paths due to being reflected, causing some signal images to arrive at the receiver antenna out of phase. This type of fading is commonly referred to as Rayleigh fading or fast fading. When a signal so fades, the signal-to-noise ratio becomes lower, causing degradation in the quality of the communication link.
A second problem occurs when the multiple signal paths have significantly different lengths. In this case, time dispersion occurs, in which multiple fading signal images arrive at the receiver antenna at different times, thereby giving rise to signal echoes or rays. This causes intersymbol interference (ISI), where the echoes of one symbol interfere with that of subsequent symbols.
At the receiver, although coherent demodulation of an incoming signal is desirable for best performance, for such coherent demodulation the characteristics of the multipath channel must be known. However, in many wireless applications, the multipath channel is time varying due to transmitter motion, receiver motion, and/or scatterer motion. Thus, there is a need to track a time varying multipath channel.
To provide coherent demodulation of multipath signals, a maximum-likelihood-sequence-estimation (MLSE) detector, such as an MLSE equalizer, may be employed. The MLSE equalizer considers various hypotheses for the transmitted symbol sequence, and, with a model of the dispersive multipath channel, determines which hypothesis best fits the received data. An MLSE equalizer may be efficiently realized using a Viterbi algorithm, which is a technique well known to those skilled in the art.
The aforedescribed conventional MLSE equalizer can better be explained by a simple example, such as also set forth in U.S. Pat. No. 5,577,068, entitled "Generalized Direct Update Viterbi Equalizer", of which the present inventor is a co-inventor. With reference now to FIG. 1 of the figures, suppose a transmitter 10, such as a mobile phone, transmits a symbol stream b(n), which takes on +1 or -1 state values corresponding to bit values 0 and 1, respectively. This symbol stream may be modulated using binary phase-shift keying (BPSK). At a receiver 20, such as a base station in a cellular telephone system, the received signal is filtered, amplified, and mixed down using I and Q carriers, then sampled once every symbol period (T), generating a received signal stream r(n). In this example, the intervening channel consists of two fading rays, a main ray and an echo, where the echo arrives T seconds later. Accordingly, the received signal can be modeled as: EQU r(n)=c.sub.0 b(n)+c.sub.1 b(n-1)+w(n) (1)
where c.sub.0 and c.sub.1 are complex channel tap values and w(n) is additive noise or interference.
In an MLSE equalizer 30 of the present example, also shown in FIG. 1, at iteration n there would be two different previous "states", 0 and 1, corresponding to the two possible values for b(n-1), i.e., +1(0) and -1(1). Associated with each previous state would be an accumulated metric, accumulated from previous iterations and giving rise to respective accumulated metrics P.sub.0 (n-1) and P.sub.1 (n-1). There would also be two current states, corresponding to the two possible values for b(n). Each possible pairing of a previous state with a current state corresponds to a hypothetical sequence {b.sub.h (n-1), b.sub.h (n)}. For each hypothesis, the predicted, hypothesized received signal value would be: EQU r.sub.h (n)=c.sub.0 b.sub.h (n)+c.sub.1 b.sub.h (n-1) (2)
The corresponding "branch" metric would be given by EQU M.sub.h (n)=.vertline.r(n)-r.sub.h (n).vertline..sup.2 (3)
The candidate metric for a current state would be the sum of the branch metric and the previously accumulated metric associated with b.sub.h (n-1). As noted, for each current state, there are two possible previous states, where the previous state which gives the smallest candidate metric is selected as the predecessor state. Accordingly, the selected candidate metric becomes the accumulated metric for that current state.
Thus, for current state 0 in the instant example, there would be two hypothetical sequences {+1, +1} and {-1, +1}, referred to as hypotheses h=00 and h=10. This gives rise to two candidate metrics: EQU C.sub.00 (n)=P.sub.0 (n-1)+M.sub.00 (n) (4a)
and EQU C.sub.10 (n)=P.sub.1 (n-1)+M.sub.10 (n) (4b)
In the present example, the smaller of these two candidate metrics gives the accumulated metric for current state 0. The corresponding previous state becomes the predecessor state to state 0 at time n. In other words, if C.sub.10 (n)&lt;C.sub.00 (n), then the accumulated metric for current state 0 at time n becomes: EQU P.sub.0 (n)=C.sub.10 (n) (5)
otherwise P.sub.0 (n)=C.sub.00 (n). The predecessor state and its predecessor and so forth are referred to as the path history of the current state. A similar procedure is applied to current state 1, in which case the two hypotheses are h=01 and h=11.
The detected symbols are decided by one of two methods. In the first method, all of the data are processed first. Then, the final state with the best metric is determined. The path history of this state (i.e. the predecessor states) gives the detected or demodulated data. In the second method, detection decisions are made before all of the data are processed. At time n, for instance, the symbol transmitted at time n-.tau. is decided, where .tau. is referred to as the decision depth. This is performed by finding the state at time n with the best metric and using its path history to determine the detected symbol at time n-.tau..
In general, the time varying channel consists of a number of channel taps that vary with time. After filtering, mixing down to baseband, and sampling, the received data samples r(n) can be modeled as: EQU r(n)=c.sub.0 (n)b(n)+c.sub.1 (n)b(n-1)+ . . . + w(n) (6)
where b(n) is the transmitted symbol stream, c.sub.i (n) are the time dispersive channel taps, and w(n) is additive noise. It is convenient to use vector notation and to express the received data samples more simply as: EQU r(n)=c.sup.T (n)x(n)+w(n) (7)
where c(n) is a vector of channel taps and x(n) is a vector containing the current and past transmitted symbols. The superscript "T" denotes the transpose.
The demodulator relies on channel tap estimates, c.sub.est (n) to predict received values for various hypothetical symbol sequences x.sub.h (n). These predicted values, referred to as target values, t.sub.h (n), are given by: EQU t.sub.h (n)=c.sub.est.sup.T (n)x.sub.h (n) (8)
The target values t.sub.h (n) are used to form branch metrics given by, for example, EQU M.sub.h (n)=.vertline.r(n)-t.sub.h (n).vertline..sup.2 (9)
or some equivalent metric. These metrics are accumulated and used to determine the demodulated symbol sequence.
The channel tap estimates must be updated to track a time-varying channel. This is done by making a tentative decision as to what symbols were transmitted up to some time n, usually less than the iteration time, and generating a string of symbols, b.sub.det (n), b.sub.det (n-1) . . . , which can be formed into a vector x.sub.det (n). Typically, an error signal e(n) is used to update the channel tap estimates, where the error signal is given by the difference in what was received and what was predicted. The error signal e(n) is given by the equation: EQU e(n)=r(n)-c.sub.est.sup.T (n)x.sub.det (n) (10)
Once the channel taps have been updated, giving c.sub.est (n+1), the channel taps can be used to form new predictions, t.sub.h (n+1). A single channel estimate is maintained or multiple channel models (one per state) can be used.
As noted, in the aforementioned MLSE detector, such as the MLSE equalizer 30 shown in FIG. 1, a sequence estimation algorithm, such as the aforedescribed Viterbi algorithm, is used to determine the most likely transmitted sequence. At each iteration, a number of possible sequences are considered, each resulting in a path metric. For each state, which corresponds to the L most recently transmitted symbols, only one set of sequences is kept, the remainder discarded or "pruned", as is understood in the art. See, for example, U.S. Pat. No. 5,191,598 to Backstrom et al. Accordingly, at each iteration, and for each state in the sequence estimation process, candidate metrics may be formed and the best one, e.g., the smallest, becomes the updated path metric. The corresponding previous symbol values then become part of the path history.
In view of the above, it is clear that the complexity of the aforementioned sequence estimation algorithm is nontrivial, particularly where the received signal depends on a greater number of bits. Accordingly, with candidate metrics formed at each iteration and for each state, a considerable amount of computational power is required to perform the requisite operations in the sequence estimation algorithm, such as within the MLSE equalizer 30.
Heretofore, "brute force" approaches have been used where all of the potential candidate metrics are first formed and then compared against one another, e.g., the aforedescribed candidate metrics C.sub.00 (n) and C.sub.10 (n) are computed and the resultant values compared. Although some techniques utilize efficient branch metrics and share computations during branch metric formation, these techniques nonetheless compute the full candidate metric, requiring a considerable number of computations, despite the efficiency savings.
Recently, other techniques have been developed for reducing complexity in the path selection (pruning) process for real signals and amplitude modulation. See, for example, M. P. C. Fossorier, "Dynamic Quantization for Maximum Likelihood Sequence Detection of PAM Signaling", IEEE Trans. Commun., Vol. 44, pp. 1444-54, November 1996. In the path selection process, for example, the symbol set is partitioned into a subset of common symbols (L-1 symbols) and a set of differing symbols (1 symbol). This allows the formation of thresholds that are applied to branch metrics or received data values. However, if this approach were extended to complex channels and phase modulation, the computation of the thresholds then becomes increasingly complicated.
It is, accordingly, an object of the present invention to reduce the amount of computation required in a sequence estimation process.
It is a further object of the present invention to provide an alternative to the aforementioned path selection techniques, such alternative being particularly useful for complex channels and phase modulation.